package katas.recursion;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class StringPermutation {
	
	public static List<String> permuteString(String s){
		if(s.length() == 0){
			return new LinkedList<String>(Arrays.asList(""));
		}
		else{
			char first = s.charAt(0);
			List<String> permutations = new LinkedList<String>();
			for(String p : permuteString(s.substring(1)))
				combine(p, first, permutations);
			return permutations;
		}
	}
	
	private static void combine(String s, char c, List<String> combinations){
		if(s.length() == 0)
			combinations.add(String.valueOf(c));
		else{
			combinations.add(s + c);
			combinations.add(c + s);
			for(int i = 1; i < s.length(); i++)
				combinations.add(s.substring(0, i) + c + s.substring(i, s.length()));
		}
	}
	
	
	private static List<String> permuteString2(String s){
		List<String> list = new LinkedList<String>();
		_permuteString(s, 0, list, new char[s.length()], new boolean[s.length()]);
		return list;
	}
	
	private static void _permuteString(String s, int i, List<String> list, char[] p, 
			boolean[] used){
		if(i == s.length()){
			list.add(String.valueOf(p));
		}
		else{
			for(int j = 0; j < s.length(); j++){
				if(used[j])
					continue;
				else{
					p[i] = s.charAt(j);
					used[j] = true;
					_permuteString(s, i+1, list, p, used);
					used[j] = false;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		String s = "12345678901";
		
		long t1 = System.nanoTime();
		StringPermutation.permuteString(s);
		System.out.println("First method in " + (System.nanoTime() - t1) + "ns");
		
		t1 = System.nanoTime();
		StringPermutation.permuteString2(s);
		System.out.println("Second method in " + (System.nanoTime() - t1) + "ns");
	}
}
